package com.lhcai.lc.other;

/**
 * @author lhcstart
 * @create 2023-02-24 17:21
 */


import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * 有重复字符串的排列组合
 * <p>
 * 有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。
 */
public class ms0808 {
    ArrayList<String> list = new ArrayList<>();

    public String[] permutation(String S) {
        char[] chars = S.toCharArray();
        dfs(chars,0);
        return list.toArray(new String[0]);
    }

    public void dfs(char[] arr, int k) {

        if (k == arr.length - 1) {
            list.add(new String(arr));
            return;
        }
        HashSet<Character> set =new HashSet<>();
        for (int i = k; i < arr.length; i++) {
            if (!set.contains(arr[i])){
                set.add(arr[i]);
                swap(arr,i,k);
                dfs(arr,k+1);
                swap(arr,i,k);
            }
        }
    }


    //简单的交换方法
    public void swap(char[] arr, int x, int y) {
        char temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

}

